#include <stdio.h>

#define N 10000
/**
 * Program 1.5 Path compression by full
 * -------------------------------------------------------
 * 算法框架：
 * - 初始化：为每个对象p构建一个以自己为元素的连通集set(p)；
 * - 循环输入整数对，对每个整数对`p-q`来说：
 *   - set(p)=find(p)，set(q)=find(q)；
 *   - 如果set(p)==set(q)，则表示p和q已经连通；
 *   - 否则，合并set(p)和set(q)
 * -------------------------------------------------------
 * 问：如何表示和操作p所在的连通集set(p)?
 * 答：树。
 *    - 集合创建操作：初始，以每个对象为根节点构建树。
 *    - 集合合并操作：当p和q表示一个新的连接时，则节点数少的树合并到节点数多的树。
 * 
 * 问：如何表示p和q连通？
 * 答：节点数少的树合并到节点数多的树。
 * 
 * 问：如何检查p和q已经连通？
 * 答：p和q所在树的根节点是否相同。
 * 
 * 问：如何表示根节点？(很关键)
 * 答：链接指向自身的对象。
 * 
 * 问：带路径压缩的加权快速合并的优化思路是什么？
 * 答：让检查到的每个节点都离根节点更近些。
 * -------------------------------------------------------
 * 借助一个整数数组id，满足如下性质：
 * - p和q是连通的当且仅当对象p所在树的根节点等于对象q所在树的根节点
 * -----------------------------------------------------
 * 实现思路:  使用树来表示连通集，借助数组id来实现树，借助数组sz来确定合并的方向
 * - 初始化id数组:  id[i] = i，构建独立树 (每个对象都是独立的树的根节点)。
 * - 循环处理输入对 p-q:
 *   - 查找根节点:  root_p = find(p), root_q = find(q)。
 *   -            让循环中遇到的每个节点都离根节点更近些。
 *   - 检查连通性:  if (root_p == root_q)，已连通，忽略。
 *   - 合并树:  否则，
 *             如果root_p所在的树包含的节点数比root_q少(sz[root_p]<sz[root_q])，则让root_p所在的树朝root_q所在的树合并，修改root_q所在树的节点计数
 *             否则，让root_q所在的树朝root_p所在的树合并，修改root_p所在树的节点计数
 *             并输出 p-q。
 * -----------------------------------------------------
 * 编译
 * gcc -o PathCompressionByFull PathCompressionByFull.c
 * -----------------------------------------------------
 * 运行
 * ./PathCompressionByFull
 * 3 4 4 9 8 0 2 3 5 6 2 9 5 9 7 3 4 8 5 6 0 2 6 1
 *
 */
int main(int argc, char **argv){
    int i, p, q, j, root;
    int id[N];
    int sz[N];

    //初始化id数组值为索引值
    for (i = 0; i < N; i++) {
        id[i] = i;
        sz[i] = 1;
    }

    // 依次处理输入对：查找+合并
    while (scanf("%d %d\n", &p, &q) == 2) {
        for (i = p; i != id[i]; i = id[i]) {
            ;
        }
        root = i;
        for (i = p; i != id[i]; i = id[i]) {
            id[i] = root;
        }
        //寻找q所在树的根节点，用j来记录
        for (j = q; j != id[j]; j = id[j]) {
            ;
        }
        root = j;
        for (j = q; j != id[j]; j = id[j]) {
            id[j] = root;
        }
        if (i == j) {
            //如果i==j(p所在树的根节点等于q所在树的根节点)，即set(p)和set(q)相等，则表示p和q相连
            continue;
        }
        if (sz[i] < sz[j]) {
            id[i] = j;
            sz[j] += sz[i];
        }else {
            id[j] = i;
            sz[i] += sz[j];
        }
        printf("%d %d\n", p, q);
    }
    return 0;
}